const arr=[30,443,18,15,17,15,15,26,37,1,46,7,20,51,90];
/**
 * 冒泡排序
 *
 */
function bubbleSort(array){
  for (let i = 0; i < array.length; i++) {
    for (let j = 0; j < array.length - 1 - i; j++) {
      if (array[j] > array[j+1]) {
        [array[j], array[j+1]] = [array[j+1], array[j]]
      }
    }
  }
  return array;
}
/**
 * 插入排序
 *
 */
function insertSort(arr) {
  let preIndex, current;
  for (let i = 1; i < arr.length; i++) {
    preIndex = i - 1;
    current = arr[i];
    while(preIndex >= 0 && arr[preIndex] > current) {
      arr[preIndex+1] = arr[preIndex];
      preIndex--;
    }
    arr[preIndex+1] = current;
  }
  return arr;
}
/**
 * 选择排序
 *
 */
function selectSort(arr) {
  let minIndex
  for (let i = 0; i < arr.length - 1; i++) {
    minIndex = i
    for (let j = i + 1; j < arr.length; j++) {
      if (arr[j] < arr[minIndex]) {
        minIndex = j
      }
    }
    [arr[i], arr[minIndex]] = [arr[minIndex], arr[i]]
  }
  return arr
}

/**
 * 希尔排序
 *
 */
function shellSort(arr) {
  var len = arr.length,
  temp,
  gap = 1;
  while(gap < len/3) {
    gap =gap*3+1;
  }
  for (gap; gap> 0; gap = Math.floor(gap/3)) {
    for (var i = gap; i < len; i++) {
      temp = arr[i];
      for (var j = i-gap; j > 0 && arr[j]> temp; j-=gap) {
        arr[j+gap] = arr[j];
      }
      arr[j+gap] = temp;
    }
  }
  return arr;
}

//console.log(bubbleSort(arr));
//console.log(insertSort(arr));
//console.log(selectSort(arr));
console.log(shellSort(arr));
